package org.example.top40;

public class main25 {
    //合并k个排序列表
    //输入：lists = [[1,4,5],[1,3,4],[2,6]]
    //输出：[1,1,2,3,4,4,5,6]
    public static void main(String[] args) {
        ListNode[] list = builder();
        ListNode res=null;
        for (int i = 0; i < list.length; i++) {
            res=meregeTwoList(res,list[i]);
        }
        System.out.println(res.val+"->"+res.next.val);
    }

    private static ListNode meregeTwoList(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 != null ? l1 : l2;
        }
        ListNode dummy = new ListNode(-1);
        ListNode pre=dummy;
        while (l1!=null&&l2!=null){
            if(l1.val>=l2.val){
                pre.next=l2;
                l2=l2.next;
            }else {
                pre.next=l1;
                l1=l1.next;
            }
            pre=pre.next;
        }
        if(l1!=null){
            pre.next=l1;
        }else {
            pre.next=l2;
        }
        return dummy.next;
    }

    private static ListNode[] builder() {
        ListNode[] result = new ListNode[3];
        ListNode nodeA1 = new ListNode(1);
        ListNode nodeA2 = new ListNode(4);
        ListNode nodeA3 = new ListNode(5);
        ListNode nodeB1 = new ListNode(1);
        ListNode nodeB2 = new ListNode(3);
        ListNode nodeB3 = new ListNode(4);
        ListNode nodeC1 = new ListNode(2);
        ListNode nodeC2 = new ListNode(6);
        nodeA1.next = nodeA2;
        nodeA2.next = nodeA3;
        nodeB1.next = nodeB2;
        nodeB2.next = nodeB3;
        nodeC1.next = nodeC2;
        result[0] = nodeA1;
        result[1] = nodeB1;
        result[2] = nodeC1;
        return result;
    }
}
